package oj;

class Solution {
    int[] sum;
    public Solution(int[] w) {
        int n=w.length;
        sum=new int[n+1];
        for(int i=1;i<=n;i++){
            sum[i]=sum[i-1]+w[i-1];
        }
    }

    public int pickIndex() {
        int m=sum.length;
        int t=(int)(Math.random()*sum[m-1])+1;
        int l=1;
        int r=sum.length-1;
        while(l<r){
            int mid=l+r>>1;
            if(t<=sum[mid]){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        return r-1;
    }
}
public class LC528 {

}
